1. Field of the Invention
The present invention relates generally to loop optimization for a computer program, and more particularly, to a method for reformulating a single exit ill-formed loop (SEIFL) such that the SEIFL is transformed into a reformulated code block that contains a transformed well-formed loop (TWFL).
2. Description of the Related Art
In order to run a computer program in a computer system, the source code of the computer program needs to be transformed into the corresponding executable machine code. The transformation from the program source code to the corresponding machine code of a computer program typically involves a computer program compiler.
When presented with a program source code, the compiler of a computer system parses the program source code, performs semantic analysis (including the generation of error messages), and produces the compiler's internal representation (IR). The compiler's IR can be optimized by the compiler and then processed by a code generator of the compiler to generate the corresponding program machine code.
The program source code often includes many loops, which typically consumes most of the execution time. Therefore, loop optimization plays a very important role in enhancing the performance of a computer system. After the program source code is processed into the compiler's IR, a loop (in the form of the compiler's IR) starts with a loop header and ends with a loop end. The code statements located between the loop header and the loop end form the loop body.
A loop of the compiler's IR can be either a well-formed loop or an ill-formed loop, depending upon the original source code of the loop. A well-formed loop does not have any loop exit statements in the loop body. However, an ill-formed loop has at least one loop exit statement in the loop body. As a result, an ill-formed loop will either exit the loop or exit the program procedure from the loop body during a program execution.
The compiler can optimize well-formed loops and generate efficient machine code, resulting in improved performance for the computer system. The compiler's optimization for a well-formed loop includes scalar optimization, loop transformation for memory locality, and automatic parallelization. However, the compiler is incapable of optimizing an ill-formed loop. As a result, inefficient machine code will be generated for a computer program with ill-formed loops, diminishing the performance of the computer system.
In view of the foregoing, there is a need for a method that can reformulate an ill-formed loop such that the ill-formed loop will be transformed into a reformulate code block that contains a transformed well-formed loop.